package com.leetcode.offer.chapter5;

/**
 * @author Dennis Li
 * @date 2020/7/15 16:59
 */
public class SearchNumber_53 {

    int pos = -1;

    public int search(int[] nums, int target) {
        // 通过二分找到位置
        binarySearch(nums, 0, nums.length - 1, target);
        if (pos == -1) return 0; // 没有出现过
        // 建立两个游标分别向前和向后探查，有无相等的节点
        int i = pos - 1, j = pos + 1, times = 1;
        while (i >= 0 || j < nums.length) {
            if (i >= 0) {
                if (nums[i--] == target) times++;
                // 第一次出现不同，那么赋值-1，不再进入这个条件判定，下面同理
                else i = -1;
            }
            if (j < nums.length) {
                if (nums[j++] == target) times++;
                else j = nums.length;
            }
        }
        return times;
    }

    // 二分查找
    public void binarySearch(int[] nums, int lo, int hi, int target) {
        if (lo > hi) return;
        int mid = (lo + hi) >> 1;
        if (nums[mid] < target) binarySearch(nums, mid + 1, hi, target);
        else if (nums[mid] > target) binarySearch(nums, lo, mid - 1, target);
        else pos = mid;
    }

}
